package listnode.question;

import listnode.ListNode;

/**题目:
 * 题意：反转一个单链表。
 * 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

 * 方法:双指针，递归
 */
//2025.04.15 百度二面
//2025.02.24 字节校招一面

//双指针法
//改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表
//首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode current=head;
        ListNode temp=null;

        while(current!=null){
            //保存下一个结点的值
            temp=current.next;
            // 翻转操作
            current.next=pre;
            //移动先移动pre,再移动current
            pre=current;
            current=temp;
        }
        return pre;
    }
}


//递归法
//和双指针法是一样的思路，只是更加简单
public class ReverseLinkList {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    //新加的函数
    private ListNode reverse(ListNode cur,ListNode pre){
        //结束条件
        if(cur==null){
            return pre;
        }
        ListNode temp=cur.next;
        cur.next=pre;

        // 更新pre、cur位置
        // pre = cur;
        // cur = temp;
        return reverse(temp, cur);
    }


}